﻿#define _CRT_SECURE_NO_WARNINGS 1


//
////邻接矩阵，指⽤⼀个矩阵(即⼆维数组)存储图中边的信息(即各个顶点之间的邻接关系)，存储顶点之间邻接关系的矩阵称为邻接矩阵。
////对于带权图⽽⾔，若顶点 vi 和 vj 之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，
//// 若顶点 vi 和 vj 不相连，则⽤ ∞ 来代表这两个顶点之间不存在边。
////对于不带权的图，可以创建⼀个⼆维的 bool 类型的数组，来标记顶点 vi 和 vj 之间有边相连。
//
//#include<iostream>
//#include<cstring>
//#include<queue>
//
//using namespace std;
//
//const int N = 1010;
//
//int n, m;
//int edges[N][N];
//
//bool st[N];//标记哪些点已经访问过
//
//
//
////DFS遍历
//void dfs(int u)
//{
//	cout << u << endl;
//	st[u] = true;
//
//	//遍历所有孩子
//	for (int v = 1;v <= n;v++)
//	{
//		//如果存在u->v的边，并且没有遍历过
//		if (edges[u][v] != -1 && !st[v])
//			dfs(v);
//	}
//}
//
////BFS遍历
//void bfs(int u)
//{
//	queue<int>q;
//	q.push(u);
//	st[u] = true;
//
//	while (q.size())
//	{
//		auto a = q.front();
//		q.pop();
//		cout << a << endl;
//
//		for (int b = 1;b <= n;b++)
//		{
//			if (edges[a][b] != -1 && !st[b])
//			{
//				q.push(b);
//				st[b] = true;
//			}
//		}
//	}
//}
//
//
////存储
////空间复杂度O（n^2），和实际边的条数无关，适合存储
//
//
//int main()
//{
//	memset(edges, -1, sizeof edges);
//
//	cin >> n >> m;//读入结点个数以及边的个数
//	for (int i = 1;i <= m;i++)
//	{
//		int a, b, c;
//		cin >> a >> b >> c;
//		//a-b有一条边，权值为c
//		edges[a][b] = c;
//
//		//如果是无向边，需要反过来再存一下 
//		edges[b][a] = c;
//	}
//
//	return 0;
//}


